package Leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 输出杨辉三角形
 * 输入: 5
 * 输出:
 * [
 *      [1],
 *     [1,1],
 *    [1,2,1],
 *   [1,3,3,1],
 *  [1,4,6,4,1]
 * ]
 */
public class L118_L119_输出杨辉三角形 {
    //公式是: [i][j] = [i-1][j-1] + [i-1][j]
    //结果是要求list，不过，直接申请一个 二维数组，做起来简单点
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<>();
        int[][] arr = new int[numRows][numRows];
        for (int i = 0; i < numRows; i++) {
            List<Integer> subList = new ArrayList<>();
            for (int j = 0; j <=i ; j++) {
                if(j==0 || j==i){//判断右边届
                    arr[i][j] = 1;
                }else{
                    arr[i][j] = arr[i-1][j-1]+arr[i-1][j];
                }
                subList.add(arr[i][j]);
            }
            list.add(subList);
        }
        return list;
    }

    //只获取特定N行，貌似是滚动数组？
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>(rowIndex);
        row.add(1);
        for(int i=1; i<= rowIndex; i++){
            row.add(1);//每行末尾+1
            for(int j=i-1; j>0 ; j--){//因为有-1，所以，j>0
                row.set(j, row.get(j-1)+row.get(j));
            }
        }

        return row;
    }

}
